package week2.prev_class.exer01;

import java.util.Scanner;

/**
 * 实验题目：第K小的数
 * 题目描述：
 * 输入n个数，求其中第k小的数。（要求采用分治法完成，不建议采用完整的排序）
 * 输入要求：
 * 第一行包含两个整数n和k；n<1000，1<=K<=n
 * 第二行包含n个整数。
 *
 * 输出要求：
 * 输出第k小的那个整数。
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        System.out.println(conquer(0, arr.length - 1, arr, k));
    }

    private static int conquer(int left, int right, int[] arr, int k) {
        int prev = left - 1;
        int cur = left;
        int pivot = arr[right];
        while (cur <= right) {
            if (arr[cur] <= pivot) {
                int tmp = arr[prev + 1];
                arr[prev + 1] = arr[cur];
                arr[cur] = tmp;
                prev++;
                cur++;
            } else {
                cur++;
            }
        }
        int leftCount = prev - left;
        if (leftCount + 1 == k) {
            return pivot;
        } else if (leftCount + 1 > k) {
            return conquer(left, prev - 1, arr, k);
        } else {
            return conquer(prev + 1, right, arr, k - (leftCount + 1));
        }
    }
}
